P1216 数字三角形

DP 入门题.

f[i][j] 代表从 $(1,1)\to (i,j)$ 的所有路径中和最大的路径

转移方程：f[i][j]=max(f[i-1][j-1],f[i-1][j])+a[i][j]

#include <bits/stdc++.h>
using namespace std;
int r;
int g[1010][1010];
int m[1010][1010];
int main()
{
    cin >> r;
    for (int i = 1; i <= r; i++)
        for (int j = 1; j <= i; j++)
            cin >> g[i][j];
    for (int i = 1; i <= r; i++)
        for (int j = 1; j <= i; j++)
            m[i][j] = max(m[i - 1][j], m[i - 1][j - 1]) + g[i][j];//正推
    // for (int i = r; i >=1; i--)
    //     for (int j = 1; j <= i; j++)
    //         m[i][j] = max(m[i + 1][j], m[i + 1][j + 1]) + g[i][j]; //反推
    int ans = 0;
    for (int i = 1; i <= r;i++)
    {
        if(m[r][i]>ans)
            ans = m[r][i];
    }
    cout <<ans << endl;
}